Search results for "Processor scheduling"
showing 8 items of 8 documents
Online Scheduling of Task Graphs on Heterogeneous Platforms
2020
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…
Use of Supercomputing towards the Generation of a Process Execution Plan in Distributed Real-Time Systems
2010
This work consider the scheduling of periodic tasks or processes with real-time constraints in a distributed environment. Each task must be executed meeting deadlines, precedence relationships and resources constraints. The problem of scheduling tasks on a distributed environment can be viewed as a problem of assigning processes to the processors but keeping the schedulability in local environments. Thus, the problem can be divided in two phases: the first phase is assigning processes to processors and the second is to schedule assigned processes in each processor in the distributed environment. This paper focuses in the first phase. It introduces a heuristic mechanism for assigning process…
Scheduling shared continuous resources on many-cores
2014
We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement rj∈[0,1]. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature. In this paper, …
Approximation algorithm for constrained coupled-tasks scheduling problem
2014
International audience; We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. In such context, we propose some complexity results according to several parameters and we design an efficient polynomial-time approximation algorithm.
Two Job Cyclic Scheduling with Incompatibility Constraints
2001
The present paper deals with the problem of scheduling several repeated occurrences of two jobs over a finite or infinite time horizon in order to maximize the yielded profit. The constraints of the problem are the incompatibilities between some pairs of tasks which require a same resource.
VarySched: A Framework for Variable Scheduling in Heterogeneous Environments
2016
Despite many efforts to better utilize the potential of GPUs and CPUs, it is far from being fully exploited. Although many tasks can be easily sped up by using accelerators, most of the existing schedulers are not flexible enough to really optimize the resource usage of the complete system. The main reasons are (i) that each processing unit requires a specific program code and that this code is often not provided for every task, and (ii) that schedulers may follow the run-until-completion model and, hence, disallow resource changes during runtime. In this paper, we present VarySched, a configurable task scheduler framework tailored to efficiently utilize all available computing resources in…
Scheduling independent stochastic tasks on heterogeneous cloud platforms
2019
International audience; This work introduces scheduling strategies to maximize the expected number of independent tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The cloud platform is composed of several types of virtual machines (VMs), where each type has a unitexecution cost that depends upon its characteristics. The amount of budget spent during the execution of a task on a given VM is the product of its execution length by the unit execution cost of that VM. The execution lengths of tasks follow a variety of standard probability distributions (exponential, uniform, halfnormal, etc.), which is known beforehand and whose mean and stand…
Latency-Oblivious Distributed Task Scheduling for Mobile Edge Computing
2018
Mobile Edge Computing (MEC) is emerging as one of the effective platforms for offloading the resource- and latency-constrained computational services of modern mobile applications. For latency- and resource-constrained mobile devices, the important issues include: 1) minimize end-to-end service latency; 2) minimize service completion time; 3) high quality-of-service (QoS) requirement to offload the complex computational services. To address the above issues, a latencyoblivious distributed task scheduling scheme is designed in this work to maximize the QoS performance and goodput for the MEC services. Unlike most of the existing works, we consider the latency-oblivious property of different …